#include <fstream>
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#include "Sorter.h"
#include "Graph.h"
#include "Set.h"
#include "PriorityQueue.h"

using namespace std;

Graph::Graph()
{
	
}
Graph::~Graph()
{
	// Release the array
	delete[] points;
	delete[] edges;
	delete[] mst;
}

void Graph::inputPoints(const std::string &filename)
{		
	// for clock
	clock_t start_t, end_t, elapsed_t;
	
	//open file
	ifstream in(filename.c_str(), ifstream::in);
	if (!in)
	{
		cerr << "Cannot open file.\n";
		exit(EXIT_FAILURE);
	}
	
	// Get number of points in file
	in >> pointsSize;
	
	// Mem alloc array of points
	try	
	{			
		points = new Point[pointsSize];
	}
	catch (bad_alloc xa) 
	{
		cerr << "Allocation Failure\n" << endl;
		exit(EXIT_FAILURE);
	}

	// Read in points line by line
	start_t = clock();
	cout << "Reading file..." << flush;	
	for (int i = 0; i < pointsSize; i++)
	{		
		Point p;
		
		in >> p.x;
		in >> p.y;

		points[i] = p;						
		//printf("File: (%f, %f)\n", p.x, p.y);
	}
	in.close();	
	
	// Print elasped time
	end_t = clock();
	elapsed_t = end_t - start_t;
	cout << "done (" << (double) elapsed_t / CLOCKS_PER_SEC << "s)" << endl;
	
	// Mem alloc array of edges
	edgesSize = (pointsSize * (pointsSize - 1)) / 2;
	try	
	{	
		edges = new Edge[edgesSize];
	}
	catch (bad_alloc xa) 
	{
		cerr << "Allocation Failure\n" << endl;
		exit(EXIT_FAILURE);
	}		
	
	/* Generate complete graph */
	cout << "Generating complete graph..." << flush;
	start_t = clock();
	edgesSize = 0;
	for (int i = 0; i < pointsSize - 1; i++)	
	{
		for (int j = i+1;j < pointsSize; j++)
		{
			//cout << "i= " << i << " j= " << j << endl;
			Edge e;
			e.index1 = i;
			e.index2 = j;

			e.cost =  sqrt(pow(points[j].x - points[i].x,2) + pow(points[j].y - points[i].y,2));;
			edges[edgesSize] = e;
			edgesSize++;
			/*
			printf("{(%f, %f),(%f,%f)} (%d, %d) = %f\n",
				points[i].x, points[i].y,
				points[j].x, points[j].y,
				i, j, e.cost);
			*/
		}
	}
	// Print elasped time
	end_t = clock();
	elapsed_t = end_t - start_t;
	cout << "done (" << (double) elapsed_t / CLOCKS_PER_SEC << "s)" << endl;
	
}

void Graph::calculateMST(Algorithm algorithm)
{
	// for clock
	clock_t start_t, end_t, elapsed_t;
	start_t = clock();
	
	cout << "Calculating MST..." << flush;
	switch (algorithm)
	{
		case prim_heap :
			prims(algorithm);
			break;
			
		case prim_unordered : 
			prims(algorithm);
			break;
			
		case kruskal_heapsort :
			kruskals(algorithm);
			break;
			
		case kruskal_mergesort :
			kruskals(algorithm);
			break;
			
		case kruskal_bubblesort :
			kruskals(algorithm);
			break;
	}	
	// Print elasped time
	end_t = clock();
	elapsed_t = end_t - start_t;
	cout << "done (" << (double) elapsed_t / CLOCKS_PER_SEC << "s)" << endl;

	
}

void Graph::outputMST(const std::string &filename)
{	
	// for clock
	clock_t start_t, end_t, elapsed_t;	
	
	cout << "Writing output to " << filename << "..." << flush;
	
	start_t = clock();
	
	// Open file for output
	ofstream out(filename.c_str(), ios::out);
	if (!out)
	{
		cerr << "Cannot open file.\n";
		exit(EXIT_FAILURE);
	}
	
	out << "<svg viewBox='0 0 1 1' width='500' height='500' xmlns='http://www.w3.org/2000/svg'>" << endl;
	
	// loop through all edges in mst
	for (int i = 0; i < pointsSize - 1; i++)
	{
		//cout << "(" << mst[i].index1 << ", " << mst[i].index2 << ")\n";
		out << "<line"
			<< " stroke='black'"
			<< " stroke-width='0.001'"
			<< " x1='" << points[mst[i].index1].x << "'"
			<< " y1='" << points[mst[i].index1].y << "'"
			<< " x2='" << points[mst[i].index2].x << "'"
			<< " y2='" << points[mst[i].index2].y << "'"
			<< " />" << endl;	
				
	}
	out << "</svg>";
	out.close();
	
	// Print elasped time
	end_t = clock();
	elapsed_t = end_t - start_t;
	cout << "done (" << (double) elapsed_t / CLOCKS_PER_SEC << "s)" << endl;

}

/* Refrenced from Design and Analysis of Algorithms
* Prims - pg 310
*/
void Graph::prims(Algorithm algorithm)
{
	PriorityQueue *pq;
	
	// Choose appropriate priority queue
	switch (algorithm)
	{
		case prim_heap :
			pq = new PriorityQueue(PriorityQueue::heap, edgesSize);
			break;
		case prim_unordered : 
			pq = new PriorityQueue(PriorityQueue::unordered, edgesSize);
			break;
		default :
			break;
	}	
	
	/* Begin Prims */
	
	// Set of tree edges
	mst = new Edge[pointsSize - 1]; 
	int t = 0; // edges in tree
	bool Vt[pointsSize]; // Set Vt	
	
	// turn off all points in Vt
	for (int i = 0; i < pointsSize; i++)
		Vt[i] = 0; // Off/Out
	
	// The set of tree vertices can be initialised with any vertex			
	Vt[0] = 1;

	while (t < pointsSize - 1)
	{			
		// populate priority queue
		for (int i = 0; i < edgesSize; i++)
		{
			// If edges are in different sets
			if (Vt[edges[i].index1] != Vt[edges[i].index2])
					pq->insert(&edges[i]);		
		}
		
		// get smallest edge
		Edge *e = pq->deleteMin();
		if (e == NULL)
		{
			printf("Breaking\n");
			break;
		}
		pq->clear();
		
		Vt[e->index1] = 1; // Vt <- Vt U {v*} - Just incase !
		Vt[e->index2] = 1; // Vt <- Vt U {u*}
		mst[t] = *e; // Et <- Et U {e*}	
		t++;
	}
	
	delete pq;
}

/* Refrenced from Design and Analysis of Algorithms
* Kruskals - pg 315
*/
void Graph::kruskals(Algorithm algorithm)
{
	// Sorter
	Sorter sorter(Sorter::merge); 
	sorter.sort(edges, edgesSize); 
	
	// Sets
	Set sets[pointsSize];
	for (int i = 0; i < pointsSize; i++)
		makeSet(&sets[i]);
		
	// Set of tree edges
	mst = new Edge[pointsSize - 1]; 
	
	int ecounter = 0;
	int k = 0;
	
	while (ecounter < pointsSize - 1)
	{
		// If edges are in different sets
		if (findSet(&sets[edges[k].index1]) != findSet(&sets[edges[k].index2]))
		{
			// Union sets
			unionSet(&sets[edges[k].index1], &sets[edges[k].index2]);
			// add edge to mst;
			mst[ecounter] = edges[k];
			ecounter++;
		}	
		k++;
	}

}

